#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    ListNode* partition(ListNode* head, int x)
    {
        if (head == nullptr)
            return head;
        ListNode* SmallListNode, * curA;
        SmallListNode = curA = new ListNode(-1);
        ListNode* BigListNode, * curB;
        BigListNode = curB = new ListNode(-1);
        while (head != nullptr)
        {
            if (head->val < x)
            {
                curA->next = head;
                curA = curA->next;
            }
            else
            {
                curB->next = head;
                curB = curB->next;
            }
            head = head->next;
        }
        curB->next = nullptr;
        curA->next = BigListNode->next;
        head = SmallListNode->next;
        delete BigListNode;
        delete SmallListNode;
        return head;
    }
};

